A. 机器学习理论

第一部分：热身题（5 分 + 1 分附加分）

本部分为选择题，每题仅选一个答案，无需说明理由。

1.（0.5 分）下列哪项最能描述偏差 - 方差权衡？

（a）增加模型偏差会降低方差，但会增加近似误差

（b）增加模型偏差会同时降低偏差和方差

（c）方差与偏差始终相互独立

（d）这种权衡仅适用于神经网络

核心概念：偏差（Bias）是模型对真实数据规律的 “欠拟合程度”（如简单线性模型无法捕捉非线性关系）；方差（Variance）是模型对训练数据噪声的 “过拟合程度”（如复杂决策树在不同训练集上预测结果差异大）。二者存在此消彼长的 “权衡” 关系。

• （a）正确：增加偏差（如用线性模型替代神经网络）会降低模型复杂度，从而减少方差（对噪声的敏感），但会因模型表达能力不足增加 “近似误差”（无法拟合真实规律的误差）。
• （b）错误：偏差和方差呈权衡关系，不可能同时降低（如降低偏差需增加模型复杂度，会导致方差上升）。
• （c）错误：二者高度相关，并非独立（模型复杂度是连接二者的关键变量）。
• （d）错误：偏差 - 方差权衡是所有机器学习模型的通用规律（如线性回归、支持向量机均适用），并非仅针对神经网络。

2.（0.5 分）“没有免费的午餐” 定理在机器学习中为何重要？

（a）每种算法在所有数据集上都表现最优

（b）所有学习任务都需要指数级时间

（c）不存在在所有任务上都普遍更优的学习算法

（d）只有平滑损失函数可被优化

核心概念：该定理（No Free Lunch Theorem, NFL）的核心是 “不存在‘万能算法’”—— 任何算法的性能都依赖于 “任务特性”（如数据分布、标签规律），在某类任务上表现好的算法，在另一类任务上可能表现差。

• （a）错误：与定理矛盾，没有算法能在所有数据集上最优。
• （b）错误：定理不涉及算法时间复杂度，仅讨论性能与任务的关系。
• （c）正确：直接对应定理核心 —— 不存在对所有任务都普遍更优的算法，选择算法需结合具体任务。
• （d）错误：定理与损失函数是否平滑无关，即使是非平滑损失（如 0-1 损失），NFL 规律依然成立。

3.（0.5 分）关于拉德马赫复杂度，下列哪项正确？

（a）它衡量假设类对随机标签的拟合程度

（b）它始终等于 VC 维

（c）随模型复杂度降低而降低

（d）与样本量无关

核心概念：拉德马赫复杂度（Rademacher Complexity）是衡量 “假设类（Hypothesis Class）拟合随机噪声能力” 的指标 —— 通过给样本随机分配 ±1 标签（拉德马赫随机变量），计算假设类对这些随机标签的预测误差，误差越小，说明假设类越容易 “死记硬背” 噪声（复杂度越高）。

• （a）正确：直接符合拉德马赫复杂度的定义 —— 衡量假设类对随机标签的拟合程度（拟合越好，复杂度越高）。
• （b）错误：拉德马赫复杂度与 VC 维是两种不同的复杂度度量（VC 维是 “打散样本” 的能力，拉德马赫是 “拟合随机标签” 的能力），无 “始终相等” 的关系。
• （c）错误：模型复杂度降低时，假设类的表达能力减弱，对随机标签的拟合能力也减弱，因此拉德马赫复杂度应降低（选项表述 “降低而降低” 逻辑矛盾，实际应为 “随模型复杂度降低而降低”，但原选项（c）表述为 “随模型复杂度降低而降低” 是正确方向？此处需注意：原选项（c）“随模型复杂度降低而降低” 是正确结论，但题目问 “哪项正确”，需对比选项 ——（a）是定义层面的正确，（c）是推导结论，但需看选项准确性：若模型复杂度降低，假设类范围缩小，拉德马赫复杂度确实降低，为何（c）错误？关键在于（a）是 “定义正确”，（c）的 “始终” 不严谨 —— 拉德马赫复杂度还与样本量相关，并非仅由模型复杂度决定，而（a）是无争议的定义表述，因此（a）更优）。
• （d）错误：拉德马赫复杂度与样本量相关 —— 样本量越大，随机标签的 “随机性” 越难拟合，拉德马赫复杂度会降低。

4.（0.5 分）在经验风险最小化（ERM）中，最小化的是什么？

（a）未见过数据的真实风险

（b）训练样本的平均损失

（c）假设类的 VC 维

（d）假设的方差

核心概念：风险（Risk）分为 “经验风险” 和 “真实风险”：

经验风险：基于训练样本计算的平均损失（如训练集中预测错误的比例）；

真实风险：基于所有可能样本计算的平均损失（无法直接计算，需通过经验风险近似）。 ERM 的目标是 “最小化经验风险”（即让模型在训练集上表现最好）。

• （a）错误：最小化真实风险是 “贝叶斯最优” 的目标，而非 ERM。
• （b）正确：直接符合 ERM 的定义 —— 最小化训练样本的平均损失。
• （c）错误：VC 维是假设类的复杂度度量，与 ERM 的优化目标无关。
• （d）错误：最小化方差是 “正则化” 的目标之一，而非 ERM。

5.（1 分）关于 VC 维，下列哪项陈述正确？

（a）VC 维无限的假设类永远无法进行 PAC 学习

（b）中半空间的 VC 维恰好为

（c）VC 维始终等于假设类的参数数量

（d）有限 VC 维意味着泛化误差为零

核心概念：VC 维（Vapnik-Chervonenkis Dimension）是衡量假设类 “表达能力” 的核心指标 —— 定义为 “假设类能打散（Shatter）的最大样本集大小”（“打散” 指对样本集的所有可能标签组合，都存在一个假设能正确预测）。

• （a）错误：VC 维无限的假设类（如所有函数构成的类）确实难以 PAC 学习，但 “永远无法” 表述绝对 —— 部分 VC 维无限的类（如带 Lipschitz 约束的函数类）可通过其他条件实现 PAC 学习。
• （b）正确：这是 VC 维的经典结论 ——空间中的半空间（如 d 维线性分类器）能打散的最大样本数为（例如 1 维半空间（区间）的 VC 维为 2，2 维半空间（直线）的 VC 维为 3）。
• （c）错误：VC 维与参数数量无直接等价关系 —— 例如，带 1 个参数的正弦函数类（），其 VC 维是无限的（可通过调整 a 拟合任意多样本）。
• （d）错误：有限 VC 维仅保证 “泛化误差可通过增加样本量降低到任意小”，而非 “泛化误差为零”（泛化误差由经验风险和置信区间组成，即使 VC 维有限，经验风险也可能非零）。

6.（1 分）在不可知 PAC 学习模型中，与可实现 PAC 模型相比，有何变化？

（a）学习者必须找到训练误差为零的假设

（b）假设类必须包含真实标签函数

（c）目标是与类中最优假设竞争，即使标签存在噪声

（d）样本复杂度与​无关

核心概念

可实现 PAC 模型（Realizable PAC）：假设 “真实标签函数属于假设类”（即存在完美拟合所有样本的假设），目标是找到训练误差为零的假设，并保证其泛化误差小。

不可知 PAC 模型（Agnostic PAC）：放松假设 ——“真实标签函数可能不属于假设类”（或标签存在噪声），目标是找到 “假设类中最优的假设”（即经验风险最小的假设），并保证其泛化误差接近类内最优假设的真实风险。

• （a）错误：这是可实现 PAC 的要求，不可知 PAC 允许训练误差非零（因标签可能有噪声或假设类不包含真实函数）。
• （b）错误：这是可实现 PAC 的前提，不可知 PAC 不要求假设类包含真实标签函数。
• （c）正确：直接符合不可知 PAC 的目标 —— 即使标签有噪声，也需与假设类内的最优假设竞争（即找到经验风险最小的假设）。
• （d）错误：不可知 PAC 的样本复杂度仍与（泛化误差容忍度）相关（样本量需随增长）。

7.（1 分）在随机梯度下降（SGD）中，使用递减学习率为何有帮助？

（a）完全避免过拟合

（b）在某些凸性假设下确保收敛

（c）增加梯度估计的方差

（d）无需反向传播

核心概念：学习率（Learning Rate）控制 SGD 每一步更新的步长：

固定学习率：若过大，易在最优解附近震荡；若过小，收敛过慢。

递减学习率（如）：前期用大步长快速逼近最优解，后期用小步长精细调整，平衡收敛速度与稳定性。

• （a）错误：递减学习率无法 “完全避免” 过拟合（过拟合需通过正则化、早停等方式缓解）。
• （b）正确：在凸优化或强凸假设下，递减学习率（如多项式衰减）可保证 SGD 收敛到最优解（固定学习率仅能收敛到最优解附近的邻域）。
• （c）错误：梯度估计的方差由 “单个样本的随机性” 决定，与学习率大小无关（递减学习率不影响方差）。
• （d）错误：SGD 无论是否使用递减学习率，都需要反向传播计算梯度（反向传播是求梯度的方法，与学习率无关）。

8.（附加题：1 分）绍尔引理关于 VC 维为d的假设类H意味着什么？

（a）H能打散任何大小大于d的集合

（b）当时，增长函数在m上多项式有界

（c）当时，经验风险最小化器的风险为零

（d）样本复杂度与d无关

*核心概念**：绍尔引理是连接 VC 维和 “增长函数”（Growth Function）的关键定理。增长函数定义为 “假设类 H 在 m 个样本上能产生的不同标签组合的最大数量”，其大小反映假设类的复杂度。 绍尔引理的结论：若假设类 H 的 VC 维为 d，则对所有，有（即当时，增长函数由指数增长变为多项式增长）。

• （a）错误：与 VC 维定义矛盾 ——VC 维为 d 意味着假设类不能打散任何大小大于 d 的集合（绍尔引理也基于此前提）。
• （b）正确：直接符合绍尔引理的推论 —— 当时，增长函数被多项式（最高次为 d 次）界定，即多项式有界。
• （c）错误：绍尔引理不涉及经验风险最小化器的风险 —— 即使，若真实函数不属于假设类，经验风险也可能非零。
• （d）错误：绍尔引理是样本复杂度分析的基础 —— 样本复杂度与 VC 维 d 正相关（d 越大，所需样本量越多），因此样本复杂度与 d 相关。

第二部分：理论题（28 分）

本部分为考试主体内容。请为每题提供详细解答和推理过程。只有完整且解释充分的答案才能获得满分。

9.（5 分）设H为符号区间类，即 ， 其中。 计算。

答案：。

• 首先证明可打散 2 个点的集合：取两点，所有 4 种标签组合（(1,1),(1,-1),(-1,1),(-1,-1)）均可由中函数实现。如 (1,-1) 可通过实现，，。
• 再证明无法打散 3 个点的集合：取，考虑标签 (1,-1,1)。中函数由区间和符号s决定，其输出在区间内外分别为s和，最多有一次符号变化，无法实现 (1,-1,1) 这种两次符号变化的标签，故不能打散 3 个点。

10.（6 分）引理证明 —— 证明以下结论成立。强凸性性质：证明下述结论成立。 设，则：

（a）函数是- 强凸的。

（b）若f是- 强凸的，g是凸的，则是- 强凸的。 （c）若f是- 强凸的，u是f的极小值点，则对任意w，有。

答案： （a）根据强凸定义，需证对任意，，。计算得，，两者差值为，满足- 强凸定义。

（b）因f - 强凸，有；g凸，有。两式相加得满足- 强凸定义。 （c）因u是极小值点，。强凸函数的一阶刻画：，代入得证。

11.（5 分）设，，H为平面上的同心圆类，即，其中。证明H是 PAC 可学习的（假设可实现性），且其样本复杂度满足。

答案：

• 可实现性下，存在使（f为真实函数）。对样本，令，取假设。
• 要证。意味着存在x使，即（若）或（若），对应区域面积A。可实现性下，样本中无x在该区域，。令，由，得，即，故H PAC 可学习且样本复杂度满足条件。

12.（7 分）初始化。在第轮，获得次梯度的随机估计，满足，并按以下方式更新迭代点：，其中是适当选择的步长参数，表示向的投影。假设F是- 强凸的，且对所有t，。考虑步长为的随机梯度下降。证明对任意，有。

答案： 由投影的非扩张性，。展开右边：。两边取期望，因，故；又。因此。

13.（5 分）神经网络是通用逼近器：设是-Lipschitz 函数。给定，构造一个使用 sigmoid 激活函数的神经网络，使得对所有，有。（提示：将划分为小盒子，利用f的 Lipschitz 性证明其在每个盒子上近似为常数，最后证明神经网络可先判断输入向量所属的盒子，再预测f在该盒子上的平均值。）

答案：

• 划分盒子：将沿各维度等分为k段，步长，得到个盒子，取k使，则f在每个盒子上的波动不超过。
• 构造盒子判断网络：对每个维度d，用 sigmoid 函数构造阈值单元，区分该维度上的区间。如对维度d的第j个区间，用（足够小）近似指示函数，组合各维度阈值单元得到盒子的指示函数。
• 构造输出层：计算每个盒子B上f的平均值，网络输出。对任意，，且，故。

B. 深度学习与强化学习

1.（9 分）神经网络架构（卷积神经网络与 Transformer）

（a）（3 分）推导输入大小为、卷积核大小为、输出通道数为（含偏置）的单个卷积层的可训练参数数量，并与相同输入输出大小的全连接（稠密）层进行比较。

（b）（3 分）写出缩放点积自注意力公式（定义Q、K、V）。解释为何 Transformer 中需要位置信息，并描述一种注入位置信息的方法。

（c）（3 分）分别说明（i）卷积在视觉任务中的一个关键优势和（ii）自注意力的一个关键优势。然后设计一个结合两种结构的最小视觉 Transformer：说明如何将图像 token 化为补丁嵌入，自注意力应用于何处，以及卷积在何处引入。

答案： （a）卷积层参数：每个卷积核有个参数，个卷积核共个，加个偏置，总参数。全连接层输入维度，输出维度（假设输出特征图大小不变），参数为。卷积层参数远少于全连接层，因共享权重且参数与输入空间大小无关。

（b）缩放点积自注意力公式：，其中Q（查询）、K（键）、V分别由输入通过线性层得到，是Q和K的维度。Transformer 无卷积的局部性，无法捕捉序列顺序，故需位置信息。注入方法：添加正弦位置编码，即，，直接与输入嵌入相加。

（c）（i）卷积在视觉中的优势：参数共享，能有效捕捉局部空间特征，计算效率高。（ii）自注意力的优势：能建模长距离依赖关系，捕捉全局上下文信息。最小视觉 Transformer 设计：将图像分为的补丁，每个补丁展平后通过线性层得到补丁嵌入；在补丁嵌入序列上应用自注意力层，捕捉补丁间全局关系；在自注意力层后插入卷积层，融合通道信息，减少维度并增强局部特征交互。

2.（14 分）生成模型与基于似然的训练

（a）（2 分）证明最大化生成模型在数据分布下的似然等价于最小化 KL 散度。

（b）（4 分）考虑由L个可逆变换组成的归一化流模型：，，，，其中每个是双射且可微的，是简单的基密度（如标准高斯分布）。写出归一化流模型在从数据分布采样的数据集上的训练目标（损失）。

（c）（4 分）解释变分自编码器（VAE）为何使用证据下界（ELBO）近似最大似然训练。写出 ELBO 表达式，并解释重建项和正则化项的作用。

（d）（4 分）我们可将扩散概率模型解释为一种分层变分自编码器（VAE）。设表示数据样本。前向过程（编码器）通过添加噪声定义为，，其中，。写出反向过程（解码器）的概率模型，并证明的 ELBO 可表示为： 答案： （a）对数似然为，KL 散度 因与无关，最大化等价于最小化。

（b）由可逆变换的变量替换公式，，其中是的雅可比矩阵。训练目标为最大化对数似然，损失函数 其中，。

（c）VAE 中，因，故，无法直接计算，故用 ELBO 近似。ELBO 表达式： 重建项使模型能从z重建；正则化项使接近先验，提高泛化性。

（d）反向过程概率模型：，其中，是高斯分布。ELBO 推导： 将，代入期望项，拆分对数并整理，利用，可得 ELBO 表达式

3.（10 分）策略梯度方法考虑折扣马尔可夫决策过程（MDP），其中状态，动作，转移核，奖励有界，折扣因子。设是可微的随机策略，参数为，是固定起始状态。定义折扣回报，性能目标，其中轨迹由和生成。

记价值函数和动作价值函数为

优势函数为。是未归一化的- 折扣状态访问分布：

（a）（6 分）证明策略梯度定理： （b）（4 分）证明对任意函数，，因此策略梯度可等价表示为 在优势方法中，应如何选择？这种选择的好处是什么？